package common.sort;

/**
 * 原理:
 * 希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；
 * 然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。
 */
public class ShellSort implements Sort {

    @Override
    public void sort(int[] array) {
        int LEN = array.length;

        // 希尔排序是进阶版本的插入排序
        for (int step = LEN / 2; step >= 1; step /= 2) {
            for (int i = step; i < LEN; i++) {
                int tmp = array[i];
                int j = i - step;

                while (j >= 0 && tmp < array[j]) {
                    array[j + step] = array[j];
                    j = j - step;
                }

                array[j + step] = tmp;
            }
        }
    }
}
